package com.veal98.bactrack;

import com.veal98.bean.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class LC257 {

    // 存储所有路径
    private List<String> res = new ArrayList<>();

    public List<String> binaryTreePaths(TreeNode root) {
        if (root == null) {
            return res;
        }

        // 存储每条路径
        List<Integer> paths = new ArrayList<>();
        backtrack(root, paths);

        return res;
    }

    private void backtrack(TreeNode root, List<Integer> paths) {
        // 当前节点加入 paths
        paths.add(root.val);

        // 结束条件：抵达叶子节点
        if (root.left == null && root.right == null) {
            // 输出 paths 路径
            StringBuilder sb = new StringBuilder();
            for (int i : paths) {
                sb.append(i).append("->");

            }
            // 删除最后一个 ->
            sb.deleteCharAt(sb.length() - 1);
            sb.deleteCharAt(sb.length() - 1);


            res.add(sb.toString());
            return ;
        }

        if (root.left != null) {
            // 进入左子树
            backtrack(root.left, paths);
            // 回溯
            paths.remove(paths.size() - 1);
        }
        if (root.right != null) {
            // 进入右子树
            backtrack(root.right, paths);
            // 回溯
            paths.remove(paths.size() - 1);
        }

    }

}
